package company.sougou;

import java.util.HashMap;
import java.util.HashSet;
import java.util.TreeSet;

public class Sou3 {

    TreeSet<String> set = new TreeSet<>();

    HashMap<String, String> dict = new HashMap<>();

    public static void main(String[] args) {
        Sou3 sou3 = new Sou3();
        System.out.println(sou3.getPasswordCount("123"));
    }


    public long getPasswordCount(String password) {
        for (int i = 0; i <= 9; i++) {
            helper(password, i, 1, String.valueOf(i));
        }
        return set.size();
    }

    private void helper(String s, int num, int index, String sb) {
        if (index == s.length()) {
            if (!sb.equals(s))
                set.add(sb);
            return;
        }
        int tmpNum = s.charAt(index) - '0';
        int next = (tmpNum + num) / 2;
        if ((tmpNum + num) % 2 != 0) {
             helper(s, next + 1, index + 1, sb + (next + 1));
        }
    }
}
